//
// Created by yanhai on 2021/1/5.
//

#include <stdio.h>
#include <string.h>

// a b c a b d  q++ next[0] = 0
// k q          q++ next[1] = 0
// k   q        q++ next[2] = 0
// k     q      k++
//   k   q      q++ next[3] = 1
//   k     q    k++
//     k   q    q++ next[4] = 2
//     k     q  k=next[k-1]
// k         q      next[5] = 0


// a b a b c a b a b a b    next[0] = 0     q++
// k q                      next[1] = 0     q++
// k   q                    k++
//   k q                    next[2] = 1     q++
//   k   q                  k++
//     k q                  next[3] = 2     q++
//     k   q                k=next[k-1]=0
// k       q                next[4] = 0     q++
// k         q              k++
//   k       q              next[5] = 1     q++
//   k         q            k++
//     k       q            next[6] = 2     q++
//     k         q          k++
//       k       q          next[7] = 3     q++
//       k         q        k++
//         k       q        next[8] = 4     q++
//         k         q      k=next[k-1]=2
//     k             q      k++
//       k           q      next[9] = 3     q++
//       k             q    k++
//         k           q    next[10] = 4     q++

void make_next(const char *pattern, int *next)
{
    int q, k;
    int m = strlen(pattern);

    // 第1个公共长度为0
    next[0] = 0;

    /**
     * q: pattern的下标
     * k: 初始状态下，k表示q指向前一位时候的最大公共长度（如果把k理解为从pattern最后开始向前移动会不会好理解些）
     *    在这个基础上，如果q位置的字母和k位置的字母依然相同，则公共长度加一，即k++
     *    如果不相等
     */
    for (q = 1, k = 0; q < m; q++) {
        while (k > 0 && pattern[q] != pattern[k])
            k = next[k - 1];

        if (pattern[q] == pattern[k]) {
            k++;
        }

        next[q] = k;
    }

    // next[0] = 0;
    // q=1, k=0, pattern[q]:pattern[k] = b:a, next[1] = 0;
    // q=2, k=0, pattern[q]:pattern[k] = c:a, next[2] = 0;
    // q=3, k=0, pattern[q]:pattern[k] = a:a, k++, next[3] = 1;
    // q=4, k=1, pattern[q]:pattern[k] = b:b, k++, next[4] = 2;
    // q=5, k=2, pattern[q]:pattern[k] = c:c, k++, next[5] = 3;
    // q=6, k=3, pattern[q]:pattern[k] = d:a, k=next[k-1] -> k=0; next[6] = 0;
}

int kmp(const char *text, const char *pattern, int *next)
{
    int n = strlen(text);
    int m = strlen(pattern);

    make_next(pattern, next);

    int i, q;
    for (i = 0, q = 0; i < n; i++) {
        while (q > 0 && pattern[q] != text[i]) {
            q = next[q - 1];
        }

        if (pattern[q] == text[i]) {
            q++;
        }

        if (q == m) {
            //printf("Pattern occurs with shift: %d\n", (i-m+1));
            break;
        }
    }

    return i - q + 1;
}

int main()
{
    int i;
    int next[20] = {0};

    char *text = "ababxbababababcdababcabddcadfdsss";
//    char *pattern = "abcabd";
    char *pattern = "ababcababab";

    int idx = kmp(text, pattern, next);
    printf("match pattern : %d\n", idx);

    for (i = 0; i < strlen(pattern); i++) {
        printf("%4d", next[i]);
    }
    printf("\n");

    return 0;
}
